/**
 * https://leetcode-cn.com/problems/binary-tree-paths/
 * 二叉树的所有路径
 * @param root 
 */
const binaryTreePaths = (root: TreeNode | null): string[] => {
    // 树为空
    if (root === null) return []

    const ans: string[] = []
    /**
     * 查找路径
     * @param n 
     * @param p 路径, 值传递
     */
    const find = (n: TreeNode | null, p: string = '') => {
        if (n == null) return;
        
        // p 不为空
        if (p !== '') p += '->'

        // 找到了叶子节点
        if (n.left === null && n.right === null) {
            ans.push(p + n.val)

            return;
        }

        p += n.val

        // 左边
        find(n.left, p)

        // 右边
        find(n.right, p);
    }

    find(root);

    return ans
};


const binaryTreePaths2 = (root: TreeNode | null): string[] => {
    // 树为空
    if (root === null) return []

    const ans: string[] = []
    let s: number[] = []
    /**
     * 查找路径
     * @param n 
     */
    const find = (n: TreeNode | null) => {
        if (n == null) return;

        // 找到了叶子节点
        if (n.left === null && n.right === null) {
            s.push(n.val)
            ans.push(s.join('->'))
            // 后退一个
            s.pop()
            return;
        }

        // 放入s中
        s.push(n.val);

        // 左边
        find(n.left)

        // 右边
        find(n.right);
        // 左右都完了
        s.pop()
    }

    find(root);

    return ans
};